package problems.contest;

import java.util.*;

/**
 * @author dubulingbo, 2023/4/2 17:27.
 */
public class BCT101 {

    /**
     * T4
     */
    public int findShortestCycle(int n, int[][] edges) {
        List<Integer>[] g = new List[n];

        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<>();
        }

        // 建图
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            int len = bfs(i, g);
            if (len != -1) {
                ans = Math.min(ans, len);
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private int bfs(int start, List<Integer>[] g) {
        int n = g.length;
        // dis[i] 表示 start 到 i 的距离
        int[] dis = new int[n];
        // -1 表示还未访问过
        Arrays.fill(dis, -1);

        Queue<Integer> que = new LinkedList<>();
        dis[start] = 0;
        que.offer(start);

        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; --i) {
                int cur = que.poll();

                for (int nxt : g[cur]) {
                    if (dis[nxt] == -1) {
                        // 从未访问过，入队
                        dis[nxt] = dis[cur] + 1;
                        que.offer(nxt);
                    } else if (dis[nxt] >= dis[cur]) {
                        // 遇到了环，因为 nxt 已经有其他的点到达过，所以可以返回
                        return dis[nxt] + dis[cur] + 1;
                    }
                    // dis[nxt] < dis[cur]，表示当前结点是从 nxt 过来的，直接忽略
                }
            }
        }

        // 没有任何环，即是一颗树，直接返回 -1；
        return -1;
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1},{1,2},{2,0},{3,4},{4,5},{5,6},{6,3}};
        System.out.println(new BCT101().findShortestCycle(7, edges));
    }
}
